from typing import List


class Solution:
    def jobScheduling(self, start_time: List[int], end_time: List[int], profits: List[int]) -> int:
        size = len(start_time)

        # 坐标压缩
        index = {num: i for i, num in enumerate(sorted(set(start_time + end_time + [10 ** 9 + 1])))}

        # 按开始时间和结束时间排序工作
        jobs = [[index[start_time[i]], index[end_time[i]], profits[i]] for i in range(size)]
        jobs.append([index[10 ** 9 + 1], index[10 ** 9 + 1], 0])  # 添加哨兵结点
        jobs.sort(key=lambda x: (x[0], x[1]))

        # dp[i] = 在结束于坐标i的最大收益
        dp = [0] * len(index)
        last = 0
        for start, end, profit in jobs:
            while last < start:
                dp[last + 1] = max(dp[last], dp[last + 1])
                last += 1
            dp[end] = max(dp[end], dp[start] + profit)

        return dp[-1]


if __name__ == "__main__":
    # 120
    print(Solution().jobScheduling(start_time=[1, 2, 3, 3],
                                   end_time=[3, 4, 5, 6],
                                   profits=[50, 10, 40, 70]))

    # 150
    print(Solution().jobScheduling(start_time=[1, 2, 3, 4, 6],
                                   end_time=[3, 5, 10, 6, 9],
                                   profits=[20, 20, 100, 70, 60]))

    # 6
    print(Solution().jobScheduling(start_time=[1, 1, 1],
                                   end_time=[2, 3, 4],
                                   profits=[5, 6, 4]))
